/*
 * Project: Code
 * File Created at 2024/1/14
 @Type Longest_Increasing_Subsequence.java
 @author Goodwin
 * Website : https://leetcode.cn/problems/longest-increasing-subsequence/?envType=study-plan-v2&envId=top-100-liked
*/

package Dynamic_Program;

public class Longest_Increasing_Subsequence {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length+2]; // todo 记录 第i个数字前(含)的 最长 严格增 子序列
        dp[0] = 1;
        int dp_max = 0;
        for (int i = 1; i < nums.length; i++) {
            int now = nums[i];
            int min = 0;
            for (int j = 0; j < i; j++) {
                if(nums[j] < now){
                    min = Math.max(dp[j], min);
                }

            }
            dp[i] = min+1;
            dp_max = Math.max(dp[i], dp_max);
        }
        return dp_max;
    }
}
